/**
 * @author ChaP
 * @date 2019/04/21
 * @describe:
 */
package CodingTest.AC20190421;
/**
 * leetcode - 395
 * 找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。

 示例 1:

 输入:
 s = "aaabb", k = 3

 输出:
 3

 最长子串为 "aaa" ，其中 'a' 重复了 3 次。
 示例 2:

 输入:
 s = "ababbc", k = 2

 输出:
 5

 最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
 */

import java.util.HashMap;
import java.util.HashSet;

public class longestSubstring {
    //未过全部测试用例
    public int longestSubstring(String s,int k){
        if(s.length() == 0) return 0;
        if(s.length() ==k) return k;
        HashMap<Character,Integer> hs = new HashMap<>();
        for(int i = 0;i<s.length();i++){
            if(hs.containsKey(s.charAt(i))){
                hs.put(s.charAt(i),hs.get(s.charAt(i))+1);
            }else {
                hs.put(s.charAt(i),1);
            }
        }
        int help[] = new int [hs.size()];

        int cur = 0;
        int pre = 0;
        int len = 0;
        for(int j = 0;j<s.length();j++){
            if(hs.get(s.charAt(j)) >= k)
            cur = j;
            else {
                if(cur == pre)len = Math.max(len,cur-pre);
                else len = Math.max(len,cur - pre+1);

                pre = cur;
            }
        }
        if(cur == pre)return Math.max(len,cur-pre);
        else
        return  Math.max(len,cur-pre+1);
    }
    //方法二：
    public int longestSubstring1(String s,int k){
        if(k<s.length()) return s.length();
        char[] c = s.toCharArray();
        int size = 0;
        for(int i =0;i<c.length;i++){
            int [] mip = new int[26];
            mip[c[i]-'a']++;
            for(int j =0;j<c.length;j++){
                mip[c[j]-'a']++;
                if(arrBiggerK(mip,k)==true && j-i+1>size){
                    size = j-i+1;
                }
            }
        }return size;

    }
        private boolean arrBiggerK(int[] arr,int k){
             for(int c:arr){
                 if(c>0 &&c<k)
                     return false;
             }
            return true;
        }
   //方法三：递归
   public int longestSubstring2(String s,int k){
        if(s == null || s.length() == 0) return 0;
        int[] book = new int[26];
        for(int i =0;i<s.length();i++){
            book[s.charAt(i)-'a']++;
        }
        //截断
        int res = 0;
        boolean flag = false;
        for(int i:book){
            if(i>0&&i<k){
                flag = true;
                break;
            }
        }
        if(flag){
            StringBuffer reg = new StringBuffer();
            for(int i =0;i<26;i++){
                if(book[i]>0 && book[i]<k){
                    reg.append((char)('a'+i)+"|");
                }
            }
            reg.deleteCharAt(reg.length()-1);
            String[] strs = s.split(reg.toString());
            for(String s1:strs){
                res = Math.max(res,longestSubstring(s1,k));
            }
        }else{
            res = s.length();
        }

        return res;
   }


    public static void main(String[] args) {
        longestSubstring ls = new longestSubstring();
        String s = "aaabb";
        int k = 3;
        System.out.println(ls.longestSubstring1(s,k));
    }
}
